//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复
//的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例： 
//
// 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
// 
// Related Topics 数组 双指针 
// 👍 2364 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Java：三数之和
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P15_ThreeSum {
    public static void main(String[] args) {
        Solution solution = new P15_ThreeSum().new Solution();
//        int[] nums = MyUtil.createFixedArray(1, 6, 0, 7, -9, 5, 3, 8, 9, 2, 0, -18);
//        int[] nums = MyUtil.createFixedArray(0, 0, 0, 0, 0, 0, 0, 0);
        int[] nums = MyUtil.createArray(-4, -1, -1, 0, 1, 2);
        Arrays.sort(nums);
        MyUtil.printInt(nums);
        // TODO 此处开始你的表演
        MyUtil.print(solution.threeSum(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    ///**
    // * 暴力求解, 解答超时
    // * 时间复杂度 O(n^3)
    // */
    //class Solution {
    //    public List<List<Integer>> threeSum(int[] nums) {
    //        Arrays.sort(nums);
    //        List list = new ArrayList();
    //        for (int i = 0; i < nums.length - 2; i++) {
    //            if (i > 0 && nums[i] == nums[i - 1]) {
    //                continue;
    //            }
    //            for (int j = i + 1; j < nums.length - 1; j++) {
    //                if (j - 1 > i && nums[j] == nums[j - 1]) {
    //                    continue;
    //                }
    //                for (int k = j + 1; k < nums.length; k++) {
    //                    if (k - 1 > j && nums[k] == nums[k - 1]) {
    //                        continue;
    //                    }
    //                    if (nums[i] + nums[j] == -1 * nums[k]) {
    //                        list.add(Arrays.asList(nums[i], nums[j], nums[k]));
    //                    }
    //                }
    //            }
    //
    //        }
    //        return list;
    //    }
    //}

    /**
     * 双指针
     * 时间复杂度 O(n^2)
     */
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List list = new ArrayList();
            for (int i = 0; i < nums.length; i++) {
                // 跳过第一层重复元素
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // j、k双指针夹逼
                int j = i + 1, k = nums.length - 1;
                while (j < k) {
                    // 跳过重复j
                    if (j > i + 1 && nums[j] == nums[j - 1]) {
                        j++;
                        continue;
                    }
                    // 跳过重复k
                    if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                        k--;
                        continue;
                    }
                    // 统计
                    int value = nums[j] + nums[k] + nums[i];
                    if (value == 0) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        j++;
                    } else if (value > 0) {
                        k--;
                    } else {
                        j++;
                    }
                }
            }
            return list;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
